package com.rong.algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 
 * @desc 希尔排序（缩小增量排序）: 是插入排序的升级版
 * 
 *       希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序
 *
 * @author liurong
 *
 * @date 2020年7月1日
 */
public class ShellSort {
	public static void main(String[] args) {
//		int[] sourceArr = new int[] { 1, 5, 12, 24, 35, 66, 100 };
		int[] sourceArr = new int[] { 12, 24, 5, 35, 2, 3, 4, -1, -100, 1, 66, 100 };
		sort(sourceArr);
		System.out.println(Arrays.toString(sourceArr));

		sourceArr = new int[100];
		for (int i = 0; i < 100; i++) {
			sourceArr[i] = new Random().nextInt(1000);
		}

		long start = System.currentTimeMillis();
		sort(sourceArr);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
		System.out.println(Arrays.toString(sourceArr));
	}

	public static void sort(int[] arr) {
		int step = arr.length / 2;
		int temp = 0;
		int k = 0;
		while (step >= 1) {
			for (int i = 0; i < step; i++) {
				for (int j = i + step; j < arr.length; j += step) {
					temp = arr[j];
					k = j - step;
					while (k >= 0 && arr[k] > temp) {
						arr[k + step] = arr[k];
						k -= step;
					}
					arr[k + step] = temp;
				}
			}
			step /= 2;
		}

	}
}
